/*
 * Selection sort is a simple sorting algorithm that improves on the performance 
 * of bubble sort. It works by first finding the smallest element using a linear 
 * scan and swapping it into the first position in the list, then finding the second
 * smallest element by scanning the remaining elements, and so on. Selection sort is 
 * unique compared to almost any other algorithm in that its running time is not affected 
 * by the prior ordering of the list, it performs the same number of operations because 
 * of its simple structure. Selection sort also requires only n swaps, and hence just Θ(n) 
 * memory writes, which is optimal for any sorting algorithm. Thus it can be very attractive
 * if writes are the most expensive operation, but otherwise selection sort will usually be 
 * outperformed by insertion sort or the more complicated algorithms.
 * 
 */

#include <iostream>
using namespace std;

void swap(int &a, int &b){
	int c=a;
	a=b;
	b=c;
}

void print_array(int* a, int n, char* sep=" "){
	for(int i=0;i<n;i++){
		cout<<a[i]<<sep;
	}
	cout <<endl;
}

int main(){
	int array[]={20,2,3,9,1,50,10,5};
	int n=sizeof(array)/sizeof(int);
	cout<<"before\n";
	print_array(array,n);

	for(int i=1;i<n;i++){
		int m=array[i];
		int k=i;
		int j=i+1;
		for(;j<n;j++){      // select out the minimal one
			if(array[j]<m){
				k=j;
				m=array[j];
			}
		}
		if(array[k]<array[i-1]){  // if the minimal one is less then the holder
			swap(array[k],array[i-1]);
		}

		//cout<< "=======\ni="<<i<<",k="<<k<<endl;
		//print_array(array,n);
	}
	
	cout<<"after\n";
	print_array(array,n);
}
